package 分治算法;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 最大子序和.java
 * @Description TODO
 * @createTime 2020年11月07日 10:41:00
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 示例:
 *
 * 输入: [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 */
public class 最大子序和 {

    class Solution {
        public int maxSubArray(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            //把当前这个数组分成三个数组 分别求解最大值
            return helper(nums, 0, nums.length - 1);
        }
        private int helper(int[] nums, int l, int r) {
            if (l > r) return Integer.MIN_VALUE;
            int mid = (l + r) >>> 1;
            int left = helper(nums, l, mid - 1);
            int right = helper(nums, mid + 1, r);
            int leftMaxSum = 0;
            int sum = 0;
            for (int i = mid - 1; i >= l; i--) {
                sum += nums[i];
                leftMaxSum = Math.max(leftMaxSum, sum);
            }
            int rightMaxSum = 0;
            sum = 0;
            for (int i = mid + 1; i <= r; i++) {
                sum += nums[i];
                rightMaxSum = Math.max(sum, rightMaxSum);
            }
            return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
        }
    }
}
